package com.bang.study.day03.heap;

import com.bang.study.day01.list.Array;
import org.apache.commons.collections4.CollectionUtils;

import java.util.*;

/**
 * @Auther: Bang
 * @Date: 2019/9/16 0016 11:43
 * @Description: 动态数组实现最小堆
 */
public class MinHeap<E extends Comparable<E>> {

    private Array<E> array;


    public MinHeap() {
        this.array = new Array<>();
    }

    public MinHeap(E[] data) {
        this.array = new Array<>(data);
        for (int i = parent(data.length-1); i > 0; i--) {
            siftUp(i);
        }
    }

    /**
     * 获取堆的大小
     * @return
     */
    public int getSize() {
        return array.getSize();
    }

    /**
     * 堆是否为空
     * @return
     */
    public boolean isEmpty(){
        return array.isEmpty();
    }

    /**
     *  获取index节点的父亲节点
     * @param index
     * @return
     */
    public int parent(int index){
        if (index==0) {
            throw new RuntimeException("index-0 doesn't hava parent");
        }
       return  (index - 1) / 2;
    }

    /**
     * index节点的左孩子所在节点的索引
     * @param index
     * @return
     */
    public int leftChild(int index){
        return (index * 2) + 1;
    }

    /**
     * index节点的右孩子所在节点的索引
     * @param index
     * @return
     */
    public int rightChild(int index){
        return (index * 2) + 1;
    }

    /**
     * 向堆中添加元素
     * @param e
     */
    public void add(E e) {
        if (isEmpty()) {
            // 当前为空 直接插入元素
            array.addLast(e);
        }else{
            array.addLast(e);
            // 最后的元素上浮
            siftUp(array.getSize() - 1);
        }
    }

    /**
     * 元素上浮
     * @param index
     */
    private void siftUp(int index) {
        while (index > 0 && array.get(parent(index)).compareTo(array.get(index)) > 0) {
            // index和其父亲进行比较,如果小于父亲,则交换位置;否则结束
            array.swap(parent(index), index);
            index = parent(index);
        }
    }

    /**
     * 元素下沉 当前index和左右孩子的最小值进行比较,如果最小值小于当前index的值,则交换位置;否则终止
     * @param index
     */
    private void siftDown(int index) {
        while (leftChild(index) < array.getSize()) {
            int j = leftChild(index);//最小节点的索引
            if ((j + 1) < array.getSize() && array.get(j).compareTo(array.get(j + 1)) > 0) {
                j = j + 1;//
            }
            if (array.get(j).compareTo(array.get(index))>0) {
                break;
            }
            array.swap(j, index);
            index = j;
        }
    }

    /**
     * 查找堆中最小元素
     * @return
     */
    public E findMin(){
        if (isEmpty()){
            throw new RuntimeException("Can't get element from empty heap");
        }else{
            E e = array.get(0);
            return e;
        }
    }

    /**
     * 取出最小元素
     * @return
     */
    public E extraMin() {
        E ret = findMin();
        // 交换首尾元素
        array.swap(0, array.getSize() - 1);
        array.removeLast();// 删除尾节点
        // 元素下沉
        siftDown(0);
        return ret;
    }


    public static void main(String[] args) {
        MinHeap<Integer> minHeap = new MinHeap<>();
        int size = 1000000;
        Random r = new Random();
        System.out.println(System.currentTimeMillis());
        for (int i = 0; i < size; i++) {
            minHeap.add(r.nextInt(Integer.MAX_VALUE));
        }
        System.out.println(System.currentTimeMillis());
        Integer min = minHeap.findMin();
        System.out.println(min);
        List<Integer> list = new ArrayList();
        while (!minHeap.isEmpty()){
            list.add(minHeap.extraMin());
        }
        System.out.println("-------------------");

        Integer[] arr = new Integer[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        System.out.println(System.currentTimeMillis());
        MinHeap<Integer> heap = new MinHeap<>(arr);
        System.out.println(System.currentTimeMillis());
        Integer minS = heap.findMin();
        System.out.println(minS);
        while (!heap.isEmpty()){
           heap.extraMin();
        }


    }



}
